﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ZYO.Algorithm
{
    public class PosfixExpression
    {
        public string midFixExpression;
        public string posFixExpression;
        
 
        public PosfixExpression()
        {
            this.midFixExpression = "";
            this.posFixExpression = "";

        }

        public PosfixExpression(string mid) : this()
        {
            this.midFixExpression = mid;
        }

        public string Parse()
        {
            StringBuilder pos = new StringBuilder();
            Stack<char> chrStack = new Stack<char>();


            char[] m = this.midFixExpression.ToCharArray(); //将字符串转成字符数组，要注意的是，不能有大于10的数存在
            int length = m.Length;

            char[] p = new char[length];

            int j = 0; // for index


            foreach(char ch in m)
            {
                if (IsOperand(ch)) //如果是操作数，直接放入p中
                {
                    p[j++] = ch;
                }
                else
                {
                    if (ch == '(')
                    {
                        chrStack.Push(ch);
                    }
                    else if (ch == ')')
                    {
                        while (chrStack.Count > 0)
                        {
                            char c = chrStack.Pop();
                            if (c == '(')
                                break;
                            else
                                p[j++] = c;
                        }
                    }
                    else //既不是'('，也不是')'，是其它操作符，比如+, -, *, /之类的
                    {
                        if (chrStack.Count > 0)
                        {
                            while (chrStack.Count > 0)
                            {
                                char c = chrStack.Pop();
                                if (Priority(ch) > Priority(c))
                                {
                                    chrStack.Push(c);
                                    chrStack.Push(ch);
                                    break;
                                }
                                else//如果栈顶元素的优先级比较高或者两者相等时
                                {
                                    p[j++] = c;
                                    if (chrStack.Count == 0)
                                    {
                                        chrStack.Push(ch);
                                        break;
                                    }
                                }
                            }
                        }
                        else//如果堆栈为空，就把操作符放入堆栈中
                        {
                            chrStack.Push(ch);
                        }
                    }

                }
            }

            while (chrStack.Count > 0)
            {
                p[j++] = chrStack.Pop();
            }

            foreach (char c in p)
            {
                if (c != '\0')//去除多余的空字符
                {
                    pos.Append(c);
                }
            }

            return this.posFixExpression = pos.ToString();
        }

        public double Calculate()
        {
            Stack<Double> myStack= new Stack<Double>();

            char[] p = this.posFixExpression.ToCharArray();
            foreach (char ch in p)
            {
                if (IsOperand(ch))
                {
                    myStack.Push((Double)(ch-48));
                }
                else
                {
                    Double n1 = myStack.Pop();
                    Double n2 = myStack.Pop();
                    myStack.Push(GetValue(ch, n1, n2));
                }
            }

            return myStack.Pop();
        }


        bool IsOperand(char c)
        {
             char[] operators = { '+', '-', '*', '/', '(', ')' };
             foreach (char ch in operators)
             {
                 if (ch == c)
                 {
                     return false;
                 }
             }

            return true;
        }

        private static double GetValue(char op, double ch1, double ch2)
        {
            switch (op)
            {
                case '+':
                    return ch2 + ch1;
                case '-':
                    return ch2 - ch1;
                case '*':
                    return ch2 * ch1;
                case '/':
                    return ch2 / ch1;
                default:
                    return 0;
            }
        }
        //返回运算符的优先级
        private static int Priority(char ch)
        {
            int priority;

            switch (ch)
            {
                case '+':
                    priority = 1;
                    break;
                case '-':
                    priority = 1;
                    break;
                case '*':
                    priority = 2;
                    break;
                case '/':
                    priority = 2;
                    break;
                default:
                    priority = 0;
                    break;
            }

            return priority;
        }

    }
}
